package com.leetcode.Demo01;
//给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
//
//
//
// 示例 1：
//
//
//输入：nums = [-2,1,-3,4,-1,2,1,-5,4]      // 思路: 找最大值--->1.求和? 求每一段的和吗? 滑块可以求出各个的
                                            // 换种方式:块执行,如果后一块与前一块比较,后块大,丢弃第一位  那么后块小咋办
//输出：6                                      // 双块吗?  如果前块大于后块,留前块   如果后块大于前块,用后块
//解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。   // 每一轮计算最大值,将值给外层
//
//
// 示例 2：
//
//
//输入：nums = [1]
//输出：1
//
//
// 示例 3：
//
//
//输入：nums = [0]
//输出：0
//
//
// 示例 4：
//
//
//输入：nums = [-1]
//输出：-1
//
//
// 示例 5：
//
//
//输入：nums = [-100000]
//输出：-100000
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 3 * 10⁴
// -10⁵ <= nums[i] <= 10⁵
//
//
//
//
// 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
// Related Topics 数组 分治 动态规划 👍 3764 👎 0


import java.util.ArrayList;
import java.util.List;

public class 最大子序和 {

    // 先试试求出每个块的值..

    public static void main(String[] args) {

        int nums[] = new int[]{-2,1,-3,4,-1,2,1,-5,4};

        int max = nums[0];
        int sum = 0;

        for (int num : nums) {
            if(sum>0){  // 前有效
                sum+=num;  // 相加
            }else {   // 前无效,舍弃
                sum = num; // 直接从当前开始加
            }

            max = Math.max(max,sum);  // 判断计数器
        }

        System.out.println(max);



        // 最小子和
        int min = nums[0];
        int sum1 = 0;
        for (int num : nums) {
            if(sum1<0){  // 前为负,有效
                sum1+=num;
            }else {  // 前为正,无效
                sum1 = num; // 定位到当前
            }

            min = Math.min(min,sum1); // 判断计数器
        }

        System.out.println(min);


        /*

        for (int i = 0; i < len; i++) {     // 定块大小
            for (int j = 0; j+i < len; j++) { // 移动块
                // 启动滑块 [j] [i+j]
                if(max<SumArea(nums, j, i + j)){
                    max = SumArea(nums, j, i + j);
                }
            }
        }


*/





//        System.out.println(SumArea(nums, 0, 2));


    }





    public static int SumArea(int arr[],int a,int b){
        int sum = 0;
        for(int i = a;i<b+1;i++){
            sum+=arr[i];
        }

        return sum;
    }


}
